/**
 * 给定一个数组A，0-index，初始位置在-1
 * 再给定M，表示可以移动M次
 * 每次可以左右移动一格，假设移动到第i格，则将Ai累加到Si
 * 等到M次移动完毕（不能移出去），问所有Si中的最小值最大能达到多少
 * 
 * 两个点：
 * 第一个比较常见，最大最小问题常见可以二分处理。
 * 第二个稍微麻烦一点，左右移动的过程，可以等价为从左到右依次横跳的过程，可以保证每一个点的入度是相等的。
 * 因此最后必然停留在最后一格或者倒数第二格。
 * 举两个例子。
 * -1 -> 0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 2
 * 可以改造为 -1 -> 0 -> 1 -> 2 -> 1 -> 2 -> 3 -> 2
 * -1 -> 0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 2 -> 3 -> 4 -> 5
 * 可以改造为 -1 0121232345
 * 可以发现到达每个点的数量是一样的多的，在本题中是等价的
 * 因此二分mid，查看是否可以通过从左到右的横跳使得每一格的得分均>=mid
 * 如果不能则返回1，否则返回0。二分搜索最后一个0的位置即可。
 * 
 * 如果是最小化最大值，只需要改一下二分即可。
 * 但如果是最小化权值总和或者最大化权值总和就应该是贪心了。
 */

using llt = long long;
using vll = vector<llt>;

llt bsLast0(llt start, llt end, function<int(llt)> f){
	assert(start <= end);
    llt left = start, right = end, mid;
	do{
        mid = (left + right) >> 1;
		auto tmp = f(mid);
		assert(0 == tmp or 1 == tmp);
		if(tmp == 1) right = mid - 1;
		else left = mid + 1; 
	}while(left <= right);
	return right;
}

class Solution {
public:
    long long maxScore(vector<int>& points, int m) {
        vll vec(points.size(), 0);
        llt limit = *max_element(points.begin(), points.end());
        limit *= m;
        auto ans = bsLast0(1, limit, [&points, m, &vec](llt mid)->int{
            auto n = points.size();
            llt times = m;
            vec.assign(n, 0LL);
            for(int i=0;i<n;++i){
                llt aleft = mid - vec[i];
                if(aleft <= 0) {
                    if(i + 1 == n) return 0;

                    times -= 1;
                    if(times < 0) return 1;
                    continue;
                }

                llt cnt = aleft / points[i];
                if(aleft % points[i]) cnt += 1;
                vec[i] += (llt)cnt * points[i];
                times -= cnt;
                times -= cnt - 1;
                if(i + 1 < n){
                    vec[i + 1] += (cnt - 1LL) * points[i + 1];    
                }else if(i){
                    vec[i - 1] += (cnt - 1LL) * points[i - 1];
                }
                if(times < 0) return 1;
            }
            return 0;
        });
        return ans;
    }
};